package com.example.algorithm.tree.heap.indexPriorityQueue;

/**
 * 索引最小优先队列
 * @param <T>
 */
public class IndexMinPriorityQueue <T extends Comparable<T>> {

    //存储堆中的元素
    private T[] items;

    //保存每个元素在items数组中的索引，pq数组需要堆有序
    private int[] pq;

    //保存pq的逆序，pq的值作为索引，pq的索引作为值
    private int[] qp;

    //记录堆中元素的个数
    private int N;


    public IndexMinPriorityQueue(int capacity){
        this.items = (T[]) new Comparable[capacity + 1];
        this.pq = new int[capacity + 1];
        this.qp = new int[capacity + 1];
        this.N = 0;

        //默认情况下，队列中没有存储任何数据,让qp中所有元素为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }

    /**
     * 获取队列中元素的个数
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return N == 0;
    }

    /**
     * 判断索引i处的元素是否小于j处的元素
     * @param i pq索引
     * @param j pq索引
     * @return i < j true
     */
    private boolean less(int i, int j){

        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    /**
     * @param i pq索引
     * @param j pq索引
     */
    private void exch(int i, int j){
        //交换pq中的数据
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;

        //更新qp中的数据
        qp[pq[i]] = i;
        qp[pq[j]] = j;

    }

    /**
     * 判断k对应的元素是否存在
     * @param k
     * @return
     */
    public boolean contains(int k){

        return qp[k] != -1;
    }

    /**
     * 返回最小元素的索引
     * @return
     */
    public int minIndex(){
        return pq[1];
    }

    /**
     * 往队列中插入一个元素，并关联索引
     * @param i
     * @param t
     */
    public void insert(int i, T t){
        //判断i是否已经被关联，如果已经被关联，则不让插入
        if (contains(i)){
            return;
        }

        //元素个数+1
        N++;
        //把数据存储到items的i位置处
        items[i] = t;
        //把i存到pq中
        pq[N] = i;
        //qp存pq的i
        qp[i] = N;

        //通过堆的上浮完成堆的调整
        swim(N);
    }

    /**
     * 删除队列中最小的元素，并返回该元素关联的索引
     * @return
     */
    public int delMin(){

        //获取最小元素关联的索引
        int minIndex = pq[1];

        //交换pq索引1处和最大索引处的元素
        exch(1,N);
        //删除qp中内容
        qp[pq[N]] = -1;
        //删除items中的内容
        items[pq[N]] = null;
        //删除pq最大索引处内容
        pq[N] = -1;
        //N--
        N--;
        //下沉算法
        sink(1);
        return minIndex;
    }

    /**
     * 删除索引i处的元素
     * @param i
     */
    public void delete(int i){
        //找到i在pq中的索引
        int k = qp[i];

        //交换pq中索引，k和N
        exch(k, N);

        //删除qp中内容
        qp[pq[N]] = -1;
        //删除items内容
        items[i] = null;
        //删除pq内容
        pq[N] = -1;
        //元素数量-1
        N--;
        //堆的调整
        sink(k);
        swim(k);
    }

    /**
     * 把索引i关联 的元素修改为t
     * @param i
     * @param t
     */
    public void changeItems(int i, T t){
        //修改items，i位置的元素为t
        items[i] = t;
        //找到i在pq中出现的位置
        int k = qp[i];
        //堆的调整
        sink(k);
        swim(k);
    }


    /**
     * 堆的上浮算法
     * @param k
     */
    private void swim(int k) {
        while (k > 1){
            if (less(k, k/2)){
                exch(k, k/2);
            }

            k = k/2;
        }
    }


    /**
     * 堆的下沉算法
     * @param k
     */
    private void sink(int k) {
        while (2 * k <= N){
            //找到子节点中的较小值
            int min;
            if (2 * k + 1 <= N){
                if (less(2*k,2*k+1)){
                    min = 2*k;
                }else {
                    min = 2*k+1;
                }
            }else {
                min = 2*k;
            }
            //比较当前结点和较小值
            if (less(k, min)){
                break;
            }
            exch(k,min);
        }
    }




}
